package club.xiaojiawei.linkedlist;

import java.util.Stack;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/23 下午11:43
 * @question 24.两两交换链表中的节点
 * @description 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
 */
public class ExchangeNode24 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        head.next.next.next.next = new ListNode(5);
//        head.next.next.next.next.next = new ListNode(6);
        ListNode result = swapPairs(head);
        System.out.println(result);
    }

    /**
     * 使用栈，迭代法
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode temp = head;
        ListNode newNode = new ListNode();
        ListNode preNode =newNode;
        Stack<ListNode> stack = new Stack<>();
        while (temp != null){
            if (stack.isEmpty()){
                stack.push(temp);
                temp = temp.next;
            }else {
                stack.peek().next = temp.next;
                temp.next = stack.peek();
                preNode.next = temp;
                preNode = temp.next;
                temp = stack.pop().next;
            }
        }
        return newNode.next;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}
